CSE 311: Foundations of Computing I

CSE 311: Homework 6 Part 2

Due: Monday, June 1st by 6:00 PM

Instructions

Write up carefully argued solutions to the following problems. Each solution should be clear enough that it can explain (to someone who does not already understand the answer) why it works. However, you may use results from lecture, the reference sheets, and previous homework without proof.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, the write up must clearly be your own, and moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution via Gradescope. In particular:

  • Each numbered task should be solved on its own page (or pages). Do not write your name on the individual pages. (Gradescope will handle that.)

  • When you upload your pages, make sure each one is properly rotated. If not, you can use the Gradescope controls to turn them to the proper orientation.

  • Follow the Gradescope prompt to link tasks to pages.

  • You are not required to typeset your solution, but your submission must be legible. It is your responsibility to make sure solutions are readable — we will not grade unreadable write-ups.

Task 1 – The Great Expression

Use the algorithm from lecture to convert each of the following regular expressions into NFAs that accept the same language. You should precisely follow the construction from lecture. In particular, you should not omit any ε\varepsilon-transitions (even between simple concatenations) or simplify the resulting NFA in any way.

  1. 10(01∪1)*11∪011010(01 \cup 1)^*11 \cup 0110

  2. (1(01∪10)*)*(1(01 \cup 10)^*)^*

Task 2 – Puedo ir(regular) al baño

Use the method described in lecture to prove that each of the following languages is not regular. You may need to get creative when constructing your prefix set and suffix!

  1. The set of all strings with properly balanced parentheses and brackets. For example, the following are balanced: “([])()([]())”, “([(())])”, “(()([]))”. The following are unbalanced: “()([])(”, “([)(])”, “]((()](”. Here is a CFG which recognizes this language: 𝐒→(S)|[S]|SS|ε\mathbf{S} \to (S) | [S] | SS | \varepsilon.

    Side note: Practically speaking, this is a basic language that any syntax checker (e.g. for Java, Python, even arithmetic expressions with parentheses, etc.) should be able to “recognize” to determine if your code is syntactically invalid! Whatever model of computation which does this must recognize more than regular languages.

  2. All binary strings in the set {0m1n:m,n∈ℕ 𝖺𝗇𝖽 m∣n}\{ 0^m 1^n : m , n \in \mathbb{N} \textsf{ and } m \mid n \} (that is, all binary strings in which the number of 0’s divides the number of 1’s). Hint: Think about the prime numbers, of which there are infinitely many.

  3. All binary strings in the set {0m1n:m,n∈ℕ 𝖺𝗇𝖽 m≤n2}\{0^m 1^n : m, n \in \mathbb{N} \textsf{ and } m \le n^2 \} (that is, all binary strings in which the number of 0’s is less than or equal to the square of the number of 1’s).

Task 3 – Last Task of the Quarter; Count Yourself Blist!

In this task, we’ll investigate various sets of lists whose elements are in {0,1}\{0, 1\}. For each part, give a proof of whether the given set is countable or uncountable. In your justification, you should use one of the following techniques, discussed in lecture:

  • Enumeration. If the elements of the given set can be listed in order, e.g. by labeling them with 0,1,2,…0,1,2,\ldots, then the given set is countable.

  • Subset. Show that the given set is a subset of another set, known to be countable. Then the given set is also countable.

  • Dovetailing. Show that the given set can be partitioned into countably many subsets, each of which is finite. Putting the subsets in order, the elements can then be enumerated in order by group, so the given set is countable.

  • Injection. Show that there is a one-to-one function f:A→Bf:A\to B. Then AA is no larger than BB.

  • Surjection. Show that there is an onto function f:A→Bf:A\to B. Then AA is no smaller than BB.

  • Diagonalization. Suppose for the sake of contradiction that the given set is countable. Then, all of its elements can be listed in order. Use the list to construct an element that is not in the list. By contradiction, the given set is uncountable.

  1. The set AA of all lists whose elements are in {0,1}\{0, 1\}. Recall that these lists can be arbitrarily long, but each particular list has finite length.

  2. The set BB of all lists with odd length and whose elements are in {0,1}\{0, 1\}.

  3. The set CC of all “infinite lists” whose elements are in {0,1}\{0, 1\}. As an analogy, you can think of one of these lists as an endless stream of 0s and 1s, such as a BitInputStream in Java.

Task 4 – Optional Practice Problems (Extra Credit)

The following problems are optional and do not need to be submitted. However, you may submit solutions and receive a small amount of extra credit for any 5 (of the 10) subparts, graded solely on completion. For the maximum extra credit score, at least 5 subparts should be submitted, including at least one subpart from each of the three sections.

  1. Convert the following NFA to a DFA.

    NFA that starts at accepting state 0. An empty string edge to state 1. State 1 goes back to state 0 with 0 (a cycle between states 0 and 1), goes to accepting state 2 with 1 and to accepting state 4 with 0. State 2 goes back to state 1 with the empty (a cycle between states 1 and 2). State 4 loops itself with the empty string and goes to accepting state 3 with the empty string.

  2. Prove that the following languages are irregular:

    1. All binary strings in the set {0n2:n∈ℕ}\{0^{n^2}:n\in\mathbb{N}\}. That is, the set of strings containing only 0s, and the number of 0s is a perfect square. Hint: Use the language itself as the distinguishing set!

    2. All binary strings in the set {0m1n:m,n∈ℕ and gcd(m,n)=1}\{0^m1^n: m,n\in\mathbb{N}\text{ and }\gcd(m,n) = 1\}. Hint: You may use the fact that there are infinitely many prime numbers.

    3. All binary strings in the set {0m1n0m:m,n∈ℕ}\{0^m1^n0^m:m,n\in\mathbb{N}\}.

    4. All binary strings in the set {0m1n:m,n∈ℕ and m<2n}\{0^m1^n: m,n\in\mathbb{N}\text{ and }m<2n\}.

  3. Countability problems:

    1. Determine whether set of functions f:ℕ→{0,1,2,3}f:\mathbb{N}\to\{0,1,2,3\} is countable or uncountable. Prove your answer.

    2. Determine whether ℕ×ℝ\mathbb{N}\times\mathbb{R} is countable or uncountable. Prove your answer.

    3. Determine whether the set of odd integers is countable or uncountable. Prove your answer.

    4. Prove that the set of all lists over the integers is countable. That is, the elements of each list can be any integer in ℤ\mathbb{Z}, which is not finite! Hint: First, prove that for each k≥0k\geq 0, the set of all lists of length kk over ℤ\mathbb{Z} is countable. Then, use the fact proved in Task 3d of Section 6.

    5. Determine whether the set of rooted binary trees with no data is countable or uncountable. Prove your answer.